﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0065_MaxArea : IAlgorithm
    {
        // 11. 盛最多水的容器

        // 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
        // 在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
        // 说明：你不能倾斜容器。

        // 提示：
        //  n == height.length
        //  2 <= n <= 10^5
        //  0 <= height[i] <= 10^4

        public void Test()
        {
            // 算法参数定义
            var height = new int[] { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
            // 算法执行与打印
            Console.WriteLine(MaxArea(height));
        }

        // 算法
        public int MaxArea(int[] height)
        {
            int res = 0, l = 0, r = height.Length - 1;
            while (l < r)
                res = height[l] < height[r] ?
                    Math.Max(res, (r - l) * height[l++]) :
                    Math.Max(res, (r - l) * height[r--]);
            return res;
        }
    }
}
